Để ổn định về hành chính trong việc khai thác thuộc địa lần thứ nhất, Pháp chia Nam Kỳ thành 20 tỉnh. Lúc bấy giờ, Cà Mau là vùng đất thuộc Rạch Giá của tỉnh Bạc Liêu.
Ngày 22 tháng 10 năm 1956, tỉnh Cà Mau được đổi tên thành tỉnh An Xuyên.
Dưới thời Việt Nam Cộng hòa tỉnh Cà Mau mang tên An Xuyên, còn tỉnh lỵ có tên là Quản Long. Tỉnh An Xuyên gồm sáu quận: Quản Long, Thới Bình, Đầm Dơi, Cái Nước, Sông Ông Đốc và Năm Căn. Dân số tính đến năm 1971 là 279.113 người.
Tuy nhiên, chính quyền Mặt trận Dân tộc Giải phóng Miền Nam Việt Nam và sau này là Chính phủ Cách mạng lâm thời Cộng hòa Miền Nam Việt Nam cùng với Việt Nam Dân chủ Cộng hòa không công nhận tên gọi tỉnh An Xuyên mà vẫn gọi theo tên cũ là tỉnh Cà Mau.
